Finite state automata are used in various fields such as natural language processing and pattern recognition. For example, a finite state automaton (FSA) is used for searching for a specific character string or a character string pattern appearing in sentences. The finite state automata are called finite automata or finite state machines (FSMs) in some cases.
An FSA that takes into consideration weights besides input symbols used in the FSA is called a weighted finite state acceptor (WFSA). An FSA that takes into consideration output symbols is called a finite state transducer (FST). An FSA that takes into consideration weights and output symbols is called a weighted finite state transducer (WFST). The WFST is used for expressing a dictionary and a model necessary for pattern recognition such as speech recognition, handwriting character recognition, and optical character recognition (OCR), and used for statistical machine translation.
A WFST that converts subwords into words, hereinafter described as L, is used for the pattern recognition that outputs a word or a word string as a recognition result using the WFST. The subwords are elements of the words. When no weights are required, L is sometimes expressed by the FST. For allowing a pattern recognition device to recognize a new word (herein after described as an additional word) not included in L, some techniques have been proposed. In one technique, the additional word is added to L. In another technique, a path relating to the additional word is embedded in a WFST that represents a language model, hereinafter described as G, without adding the additional word to L.
In such conventional techniques, L or G is changed by embedding the path corresponding to the additional word in L or G. This change makes it difficult to share the WFST among a plurality of pattern recognition devices when the pattern recognition devices need to recognize the different additional words from one another.